package 简单.模拟;

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

/**
 * 给你一个非负整数数组 nums 。在一步操作中，你必须：
 * 选出一个正整数 x ，x 需要小于或等于 nums 中 最小 的 非零 元素。
 * nums 中的每个正整数都减去 x。
 * 返回使 nums 中所有元素都等于 0 需要的 最少 操作数。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/make-array-zero-by-subtracting-equal-amounts
 */
public class 使数组中所有元素都等于零_2357 {

    public static void main(String[] args) {

    }

    /**
     * 排序+模拟
     */
    public int minimumOperations(int[] nums) {
        Arrays.sort(nums);
        int idx = 0;
        int cnt = 0;
        while (idx < nums.length) {
            while (idx < nums.length && nums[idx] == 0) {
                idx++;
            }
            if (idx == nums.length) break;
            cnt++;

            int min = nums[idx];
            for (int i = idx; i < nums.length; i++) {
                nums[i] -= min;
            }
            idx++;
        }
        return cnt;
    }

    /**
     * 贪心+哈希表
     * 最少操作次数为除了 0 之外的不同数字数量
     */
    public int minimumOperations2(int[] nums) {
        Set<Integer> set = new HashSet<>();
        for (int num : nums) {
            set.add(num);
        }
        set.remove(0);
        return set.size();
    }

}
